#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MAXN = 1e5+7;
LL arr[MAXN];
LL cnt[MAXN];
LL a[MAXN];
LL prime[MAXN], p_cnt;
bool not_p[MAXN];
LL tree[MAXN];
void Init() {
    p_cnt = 0;
    tree[1] = 1;
    for (LL i=2; i<MAXN; ++i) {
        if (!not_p[i]) {
            prime[p_cnt++] = i;
            tree[i] = 1;
        }
        for (LL j=0; j<p_cnt&&i*prime[j]<MAXN; ++j) {
            tree[i*prime[j]] = i;
            not_p[i*prime[j]] = true;
            if (i%prime[j] == 0) {
                break;
            }
        }
    }
}
LL p_list[20], l_cnt;
void Feijie(LL ask) {
    l_cnt = 0;
    LL t = ask;
    while (t!=1) {
        if (l_cnt==0 || p_list[l_cnt-1] != t/tree[t]) p_list[l_cnt++] = t/tree[t];
        t = tree[t];
    }
}

int main() {
#ifdef hai
    freopen("in.txt", "r", stdin);
#endif
    Init();
    LL T, n;
    scanf("%lld", &T);
    while (T--) {
        memset(cnt, 0, sizeof(cnt));
        LL _max = 0;
        scanf("%lld", &n);
        for (LL i=0, t; i<n; ++i) {
            scanf("%lld", &t);
            if (t>_max) _max = t;
            ++cnt[t];
            arr[i] = t;
        }
        for (LL i=1; i<=_max; ++i) {
            LL &t = a[i];
            t = 0;
            for (LL k=1; k*i<=_max; ++k) {
                t += cnt[k*i];
            }
        }
        LL res = 0;
        for (LL i=0; i<n; ++i) {
            Feijie(arr[i]);
            LL len = (1<<l_cnt);
            LL cc = 0;
            for (LL j=1; j<len; ++j) {
                LL p = 1;
                LL mu = 0;
                for (LL k=0; k<l_cnt; ++k) {
                    if (j&(1<<k)) {
                        p *= p_list[k];
                        ++mu;
                    }
                }
                if (mu&1) mu = 1;
                else mu = -1;
                cc += mu*a[p];
            }
            if (arr[i] == 1) cc = n;
            res += (cc-1)*(n-cc);
        }
        res /= 2;
        res = n*(n-1)*(n-2)/6 - res;
        printf("%lld\n", res);
    }
    return 0;
}
